package com.zhang;

/**
 * @author ZhangJiXin
 * @Description UnionFind -- QU(快速合并) -- R(高度) -- PC(路径压缩)优化
 * @date 2021/4/30 9:52
 */
public  class UnionFind_QU_R_PC extends UnionFind_QU_R {

    public UnionFind_QU_R_PC(int capacity) {
       super(capacity);
    }

    /**
     * 路径压缩就是在查找根节点的时候
     * 将路径上所有元素都指向根节点
     * 从而让树的高度变矮 使得更加平衡
     * @Author ZhangJiXin
     * @Date 2021/4/30 15:09
     * @param v:
     * @return: int
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        if (v != parents[v]){
            parents[v] = find(parents[v]);
        }
        return parents[v];
    }
}
